#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

typedef int ElemType;
typedef struct {
    ElemType *elem;
    int TableLen;
}SSTable;
//初始化顺序表
void ST_Init(SSTable &ST,int len)
{
    ST.TableLen=len;
    ST.elem=(ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    srand(time(NULL));  //随机生成数
    for (int j = 0; j < ST.TableLen; j++)
    {
        ST.elem[j]=rand();
    }
}
void ST_Print(SSTable ST)
{
    for (int i = 0; i < 10; ++i) {
        printf("%6d",ST.elem[i]);
    }
    printf("\n");
}
void swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
//把某个子树调整为大根堆
void AdjustDown(ElemType *A,int k,int len)
{
    int dad=k;  //父亲的下标
    int son=2*dad+1; //左孩子下标
    while (son<len)  //孩子结点下标不超过长度
    {
        if(son+1<len&&A[son]<A[son+1]) //如果左孩子小于右孩子,而且要判断存在右孩子
        {
            son++; //拿右孩子
        }
        if(A[son]>A[dad]) //如果孩子大于父亲
        {
            swap(A[son],A[dad]); //交换元素
            dad=son;  //孩子作为新的dad,取判断下面的子树是否符合大根堆
            son=2*dad+1;
        } else{
            break;
        }
    }
}
void HeapSort(ElemType *A,int len)
{
    int i,j;
    //先对前10个元素建立大根堆
    for (i=len/2-1;i>=0;i--)   //len/2-1 最后一个子树的父节点
    {
        AdjustDown(A,i,len);
    }
    //比较剩余的A[10]到A[99999]元素，小于堆顶，就放入A[10]，继续调整10个元素为大根堆
    for (j=10;j<100000;j++)
    {
        if(A[j]<A[0])
        {
            A[0]=A[j];
            AdjustDown(A,0,10);    //继续调整为大根堆
        }
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,100000);
//    ST_Print(ST);
    HeapSort(ST.elem,10);
    ST_Print(ST);
    return 0;
}
